import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

public class Solution {

    /**
     * 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target 的 所有不同组合 ，
     * 并以列表形式返回。你可以按 任意顺序 返回这些组合。
     * <p>
     * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
     * 对于给定的输入，保证和为target 的不同组合数少于 150 个。
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> combine = combine(candidates, target, 0, 0);
        if (Objects.isNull(combine)){
            return Collections.emptyList();
        }
        return combine;
    }

    public static List<List<Integer>> combine(int[] candidates, int target, int base, int preIdx) {
        List<List<Integer>> result = null;
        for (int i = preIdx; i < candidates.length; i++) {
            int cur = candidates[i];
            int sum = base + cur;
            if (sum < target) {
                List<List<Integer>> subResult = combine(candidates, target, sum, i);
                if (Objects.nonNull(subResult)) {
                    subResult.forEach(e -> e.add(0, cur));
                    if (Objects.isNull(result)) {
                        result = subResult;
                    } else {
                        result.addAll(subResult);
                    }
                }
            } else if (sum == target) {
                if (Objects.isNull(result)) {
                    result = new ArrayList<>();
                }
                List<Integer> list = new ArrayList<>();
                list.add(cur);
                result.add(list);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] candidates = new int[]{2, 3, 5};
        System.out.println(combinationSum(candidates, 8));
    }

}